1. Field of the Invention
The present invention relates to image processing techniques. More specifically, the present invention relates to techniques for associating targets or objects in a first frame of data with targets or objects in a second frame of data.
While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those having ordinary skill in the art and access to the teachings provided herein will recognize additional modifications, applications and embodiments within the scope thereof.
2. Description of the Related Art
Targets and objects representing electro-optical or electromagnetic observations, detections and measurements may be represented as a sequential tabulation of discrete events in two dimensions, along with associated attributes (i.e. intensity). The events are typically represented by a frame of data from a scanning, or periodically sampled staring, sensing system. Each frame of data results from one scan, of a scanning sensor, or one sampling interval for a staring sensor. In any event, the problem is to efficiently associate targets from one frame to targets in another frame. In this context, efficiency is a measure of the speed and accuracy by which the targets may be associated. In general, the number of calculations required by a particular target association technique has a significant impact on the efficiency and power consumption of the technique.
In this connection, there are several significant limitations associated with conventional target association techniques. First, conventional target association techniques typically require too many calculations to be sufficiently fast and efficient to address many demanding contemporary applications. That is, target association from scan to scan is typically performed on the basis of some cost function relating target i of scan N-1 to target j of scan N. For each i,j pair, there is an associated cost C.sub.ij (e.g. the mean square error) between the targets. The association that minimizes the total cost Z=Sum C.sub.ij, while constraining any association to be one for one, is the desired solution. If there are M targets in each frame, then there are M factorial (M-) possible associations from which to choose the correct target m. Clearly enumeration (the individual calculation of the cost corresponding with each possible association) would be too expensive for more than just a few targets. For example, one current application requires the rapid, efficient and accurate association of approximately 10,000 to 30,000 objects including targets, stars and ground clutter. There is therefore a current need in the art for a fast, accurate and efficient target association technique.
Secondly, conventional techniques do not necessarily provide an optimal solution to a particular target association problem. That is, the required one to one correspondence on the solution set which in turn forces removal and replacement of associated targets, disallows the assumption of convexity. If the feasible solutions were a convex set, one could proceed along the direction of maximum slope from basic feasible solution to basic feasible solution until an optimum solution was achieved. However, this procedure fails where the solution sets are not convex, i.e. have local extremals. There is therefore a further need in the art for a target association technique that more frequently provides an optimal solution than conventional techniques.
Finally, conventional techniques are typically too theoretical and general with no practical constraints to be of practical utility for a particular application. While these techniques may provide for accurate association, they often assume no practical constraints with respect to time, memory, number of targets etc. There is therefore a need in the art for an accurate, practical, efficient, fast and reliable target association technique.
The need in the art is addressed by the improved target association method of the present invention. The method of the invention includes the steps of:
(a) generating electrical or optical signals representing target detections from an image sensor;
(b) storing the signals from a first detection interval in a first memory as a first frame of data;
(c) storing the signals from a second detection interval in a second memory as a second frame of data;
(d) generating a matrix of cost functions having n rows corresponding to n targets from the first frame of data and m columns corresponding to m targets in the second frame of data, each cost function being a function of one of n targets in a first frame of data and one of m targets in a second frame of data;
(e) ordering the rows of the matrix by:
(i) computing for each row a value equal to the difference between the two smallest cost functions in the row; PA0 (ii) identifying and selecting as an initial starting row, the row with the largest difference value, and removing from consideration for the calculation of difference values for subsequent rows, the column in which the smallest cost function in the row is located; PA0 (iii) setting the selected row as the first row in the order; PA0 (iv) calculating the difference values for subsequent rows; PA0 (v) setting as the next row in the order the row providing the largest difference value of the remaining rows, if the row has a difference value larger than that of any previously selected row, then recomputing the difference values for the previously selected rows removing from consideration for the calculation of the difference values the column in which the smallest cost function in the currently selected row is located; PA0 (vi) ordering the selected rows according to difference values; PA0 (vii) repeating steps (iv) through (vi) beginning with the last selected row, if the selected row is the last row, then PA0 (i) computing for each row a value equal to the difference between the two smallest cost functions in the row; PA0 (ii) identifying and selecting as an initial starting row, the row with the largest difference value, and removing from consideration for the calculation of difference values for subsequent rows, the column in which the smallest cost function in said row is located; PA0 (iii) setting as the first row in said order said first selected row; PA0 (iv) calculating the difference values for subsequent rows; PA0 (v) setting as the next row in said order the row providing the largest difference value of the remaining rows, if the row has a difference value larger than that of the initial starting row, then selecting, as a new first row, the row with the largest difference value, replacing the previously removed columns, removing, from subsequent calculations to obtain the difference values for subsequent rows, the column in which the smallest cost function in said row is located and returning to step iii) to begin a new pass through said matrix, otherwise; PA0 (vi) removing the column in said next row in which said smallest cost function is located and PA0 (iv) repeating steps v-vi until said n rows have been ordered; then
(f) associating, for each row in accordance with the order of the rows, the signal from the target corresponding to the row with the signal from the target corresponding to the column, not previously associated, having the smallest cost function so that each signal corresponding to each target from the first frame of data is optimally associated with a signal corresponding to a single target in the second frame of data.
The limitations of conventional targets association techniques are addressed by the improved target association technique of the present invention.
The improved target association method of the present invention includes the steps of:
(a) generating a matrix of cost functions having n rows corresponding to n targets from a first frame of data and m columns corresponding to m targets in a second frame of data, each cost function being either a function of one of n targets in a first frame of data and one of m targets in a second frame of data, or a dummy value;
(b) ordering the rows of said matrix by:
(c) associating, for each row in accordance with said order of said rows, the target corresponding to the row with the target corresponding to the column, not previously associated, having the smallest cost function so that each target from said first frame of data is optimally associated with a single target in said second frame of data.